class Solution {
public:
    int dp[110];
    
    int numDecodings(string s) {
        dp[0] = 1;
        dp[1] = s[0] == '0' ? 0 : 1;
        for (int i = 2; i <= s.size(); i ++ ) {
            if (s[i - 1] != '0') dp[i] = dp[i - 1];
            int t = stoi(s.substr(i - 2, 2));
            if (t >= 10 && t <= 26) dp[i] += dp[i - 2];
        }
        return dp[s.size()];
    }
};
